f) (25 bodov) Učiteľ napokon s vašou pomocou zradné úlohy vyriešil. Predtým, ako môže ísť za kamarátmi, musí ale žiakov odviesť na obed a robiť počas neho dozor. Preto by chcel, aby to trvalo čo najkratší čas. To samozrejme závisí od prejdenej vzdialenosti. Prečítajte rozmery mapy školy R a C, (3 <= R,C <= 54) a na následných R riadkoch samotnú mapu. Na každom z týchto riadkov je práve C znakov, ktoré sú alebo X (stena), alebo . (bodka, chodba). Okrem týchto znakov je práve jeden znak T (trieda) a práve jeden znak M (mäso). Na výstup vypíšte jediné číslo : dĺžku najkratšej cesty medzi triedou a jedálňou. Dĺžku cesty meriame v krokoch medzi políčkami, pričom za susedné políčka považujeme tie, medzi ktorými je hrana (políčko má najviac štyroch susedov). Môžete predpokladať, že okrajové rady a stĺpce nákresu sú steny.

Príklad:

Vstup:

4 15

XXXXXXXXXXXXXXX
X..X......XXXMX
XX..T.XX......X
XXXXXXXXXXXXXXX

Výstup:

12

Vstup:

20 51

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X..................X..............................X
X........X.......T.X....XXXXXXXXXXXXXXXXXXXXXX....X
X.XXXXXXXXXXXXXXXXXX....X....................X....X
X..................X....X....XXXXXXXXXXXX....X....X
X..................X....X....X..........XX.XXX....X
XXXXXXXXXXXXXXXXX..X....X....X....................X
X..................X....X....XXXXXXXXXXXXXXXXXXXXXX
X.......XXXXXXXXXXXXXXX.X....................X....X
X..................X....X..XXXXXXXXXXXXXXXXXXXXXXXX
X..................X....X.........................X
X..................X....XXXXXXXXXXXXXXXXXXXXXX....X
X.XXXXXXXXXXXXXXXXXX.XXXX....................X....X
X..................X....X....XXXXXXXXXXXX....X....X
X..................X....X....X..M.......XX...X....X
XXXXXXXXXXXXXXXXX..X....X....X...............X....X
X..................X....X....XXXXXXXXXXXXXXXXXXXX.X
X.......XXXXXXXXXXXXXXX.X....................X....X
X.......................X.........................X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Výstup:

275

---